home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _bicomponents.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  3.0 KB  |  111 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _bicomponents.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  BICONNECTED COMPONENTS                                                      *
  20. *                                                                              *
  21. *  Michael Meiser (1991)                                                       *
  22. *                                                                              *
  23. *******************************************************************************/
  24.  
  25. #include <LEDA/graph_alg.h>
  26. #include <LEDA/stack.h>
  27.  
  28.  
  29.  
  30. static void bcc_dfs(const ugraph& G,node v,edge_array<int>& compnum,
  31.                     node_array<int>& dfsnum,node_array<int>& lowpt,
  32.                     node_array<node>& father,stack<node>& current,
  33.                     int& count1,int& count2);
  34.  
  35.  
  36. int BICONNECTED_COMPONENTS(const ugraph& G, edge_array<int>& compnum)
  37. {
  38.   // computes the biconnected components of an undirected graph G
  39.   // returns m = number of biconnected components
  40.   // returns in edge_array<int> compnum for each edge an integer with
  41.   // compnum[x] = compnum[y] iff edges x and y belong to the same component 
  42.   // and 0 <= compnum[e] <= m-1 for all edges e
  43.   //  running time : O(|V|+|E|)
  44.   //
  45.   // (problem  with self-loops ? )
  46.  
  47.   stack<node> current;
  48.   node_array<int> dfsnum(G,-1);
  49.   node_array<int> lowpt(G,0);
  50.   node_array<node> father(G,nil);
  51.   int count1 = 0; 
  52.   int count2 = 0;
  53.   node v;
  54.  
  55.   forall_nodes(v,G)
  56.    if (dfsnum[v] == -1)
  57.     {
  58.      dfsnum[v] = ++count1;
  59.      current.push(v);
  60.      bcc_dfs(G,v,compnum,dfsnum,lowpt,father,current,count1,count2);
  61.     }
  62.  
  63.   return(count2);
  64.  
  65.  } // BI_COMPONENTS
  66.  
  67.  
  68.  
  69. static void bcc_dfs(const ugraph& G,node v,edge_array<int>& compnum,
  70.                     node_array<int>& dfsnum,node_array<int>& lowpt,
  71.                     node_array<node>& father,stack<node>& current,
  72.                     int& count1,int& count2)
  73.  {
  74.   node w;
  75.  
  76.   lowpt[v] = dfsnum[v];
  77.  
  78.   forall_adj_nodes(w,v)
  79.    if (dfsnum[w] == -1)
  80.     {
  81.      dfsnum[w] = ++count1;
  82.      current.push(w);
  83.      father[w] = v;
  84.      bcc_dfs(G,w,compnum,dfsnum,lowpt,father,current,count1,count2);
  85.      lowpt[v] = Min(lowpt[v],lowpt[w]);
  86.     }
  87.    else
  88.     lowpt[v] = Min(lowpt[v],dfsnum[w]);
  89.  
  90.   if (father[v] && (lowpt[v] == dfsnum[father[v]]))
  91.    // 1.Bedingung nur von Bedeutung fuer Graphen,die nicht zusammen-
  92.    // haengend sind sowie fuer den ersten besuchten Knoten
  93.    {
  94.     edge e;
  95.  
  96.     do
  97.      {
  98.       w = current.pop();
  99.       forall_adj_edges(e,w)
  100.        if (dfsnum[w] > dfsnum[G.opposite(w,e)])
  101.         compnum[e] = count2;
  102.      }
  103.     while (w != v);
  104.  
  105.     count2++;
  106.    }
  107.  
  108.  } // bcc_dfs
  109.  
  110.  
  111.